# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
# class Solution:
#     def EntryNodeOfLoop(self, pHead):
#         # write code here
#         nodes = []
#         while pHead:
#             if pHead not in nodes:
#                 nodes.append(pHead)
#                 pHead = pHead.next
#             else:
#                 return pHead
#         return None
# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        '''
        这样做是基于一个方程，设快的和慢的都走了x步，那么快的和慢的要碰到一起只有快的比慢的夺走了一圈
        2*x = c*(n + 1) + b
        x = c*n + b
        x为走的步数， c为一圈的距离，n为圈数，b为圈外部分的步数
        x = c
        所以慢的一共走了c步，距离交点还剩b步，这样如果一个点从起点开始走的话正好可以和慢的点在循环的起始点相遇
        :param pHead:
        :return:
        '''
        if not pHead:
            return None
        fast = pHead
        slow = pHead
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                slow2 = pHead
                while slow2 != slow:
                    slow = slow.next
                    slow2 = slow2.next
                return slow
        return None





# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        if not pHead or not pHead.next:
            return None
        step = 0
        low_start = pHead.next
        fast_start = pHead.next.next
        use_break = False
        while fast_start and fast_start.next:
            step += 1
            if low_start == fast_start:
                use_break = True
                break
            low_start = low_start.next
            fast_start = fast_start.next.next
        if not use_break:
            return None
        fast = pHead
        for i in range(step):
            fast = fast.next
        slow = pHead
        while slow != fast:
            slow = slow.next
            fast = fast.next
        return slow
